package offer.offer03;

/**
 * 或者Arrays.sort(nums)然后返回中间的数, 也行。
 */
public class S39数组中出现次数超过一半的数字 {
    /**
     * 99, 第二次遇到, 试一下上一次的摩尔投票法。
     * 如果不是确定有这么个数的话, 还需要在选出toVote之后做一个校验,
     * 另外强化的题目包括 找出一个数组中占比超过1/3的数字
     */
    public int majorityElement(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        int toVote = nums[0];
        int voteCount = 0;
        for(int i: nums){
            if(voteCount == 0) toVote = i;
            if(i == toVote)
                voteCount++;
            else
                voteCount--;
        }
        return toVote;
    }
}
